package leetcode.array;

/**
 * @Description: https://leetcode.cn/problems/majority-element/description/
 * @Author Ammar
 * @Create 2023/8/4 12:51
 */
public class _169_多数元素 {
    /**
     * Boyer-Moore 投票算法
     * 如果我们把众数记为 +1+1+1，把其他数记为 −1-1−1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。
     * 相等 count + 1 不相等 count - 1
     * 当 count 等于 0 时，将 candidate 换成当前数，重新开始。
     */
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}
